package Datastruct.Kruskal.krusk;

import java.util.Arrays;

//克鲁斯卡尔算法
public class Kruskaler {
    public static void main(String[] args) {

        Graph graph = new Graph();
        int[][] arry = new int[7][7];
        for (int i = 0; i < 7; i++) {
            for (int j = 0; j < 7; j++) {
                if (i == j) {
                    arry[i][j] = 0;

                } else {
                    arry[j][i] = Integer.MAX_VALUE;
                }
            }
        }
        arry[0][1] = 7;
        arry[0][3] = 5;
        arry[1][2] = 8;
        arry[1][3] = 9;
        arry[2][4] = 5;
        arry[3][4] = 15;
        arry[4][5] = 8;
        arry[4][6] = 9;
        arry[5][6] = 11;

        graph.array = arry;
        int k = 0;
        Edge[] edges = new Edge[11];
        //创建结点
        for (int i = 0; i < edges.length; i++) {
            Edge edge1 = new Edge();
            edges[i] = edge1;
        }
        for (int i = 0; i < 6; i++) {
            for (int j = i + 1; j < 7; j++) {
                if (arry[i][j] < Integer.MAX_VALUE) {
                    edges[k].begain = i;
                    edges[k].end = j;
                    edges[k].weight = arry[i][j];
                    k++;
                }
            }
        }
        graph.edges = edges;
        Arrays.sort(edges);
        kruskal(graph);


    }

    /*
     * 是否构成回路
     *
     * */

    public static int findParentRoot(int terget, int[] parent) {

        while (parent[terget] > 0) {
            terget = parent[terget];
        }
        return terget;
    }

    public static void kruskal(Graph graph) {
        Edge[] edges = graph.edges;
        ;
        int[][] arr = graph.array;
        ;
        int[] parent = new int[7];
        for (int i = 0; i < edges.length; i++) {
            Edge edge = edges[i];
            int begin = findParentRoot(edge.begain, parent);
            int end = findParentRoot(edge.end, parent);
            if (begin != end) {
                System.out.println(String.format("(%d,%d)--->%d", begin, end, edge.weight));
                parent[begin] = end;
            }
        }
    }
}
